class Solution(object):
    def increasingTriplet(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if not nums: return False
        tail = []
        tail.append(nums[0])
        for i in range(1, len(nums)):
            num = nums[i]
            if num<tail[0]:
                tail[0]=num
            elif num>tail[-1]:
                tail.append(num)
                if len(tail)==3: return True
            else:
                begin=0
                end=len(tail)-1
                while begin<end:
                    mid=(begin+end)//2
                    if tail[mid]<num:
                        begin=mid+1
                    else:
                        end=mid
                print(tail, begin)
                tail[begin]=num
        return False

print(Solution().increasingTriplet([1,2,-10,-8,-7]))